ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpd/disgruntled/disgruntled.cpp

   1 #include <stdlib.h>
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <sys/types.h>
   5 #include <sys/stat.h>
   6 #include <fcntl.h>
   7 #include <cassert>
   8 #include <list>
   9 using namespace std;
  10 #define forn(i,n) for(int i = 0; i < n; ++i)
  11 #define forsn(i,s,n) for(int i = (s); i < (n); i++)
  12 #define foreachin(it,s) for(__typeof__((s).begin()) it = ((s).begin()); it != ((s).end()); ++it)
  13
  14 #define inverso_de_73_mod_137 122
  15 #define inverso_de_137_mod_73 8
  16 #define coef_137 1096 // 137*8
  17 #define coef_73 8906 // 73*122
  18
  19 static int cuad73[73];
  20 static int cuad137[137];
  21
  22 #define resto(x,y) ((((x) % (y)) + (y)) % (y))
  23
  24 // si (a,b) = 1, deja en x el inverso multiplicativo de a ,mod b
  25 // basicamente es la idea del algoritmo de euclides, pero iterativo
  26 // mas info: www.math.hawaii.edu/~lee/discrete/combination.ps
  27 void combinacion(int a, int b, int&x) {
  28     int g0 = a;
  29     int x0 = 1;
  30 //    int y0 = 0;
  31     int g1 = b;
  32     int x1 = 0;
  33 //    int y1 = 1;
  34     while (g0 % g1 != 0) {
  35 //invariante: a*x_1+b*y_1=g1
  36         int q = g0 / g1;
  37         int temp = g1;
  38         g1 = g0 - q * g1;
  39         g0 = temp;
  40         temp = x1;
  41         x1 = x0 - q * x1;
  42         x0 = temp;
  43         /*
  44                 temp = y1;
  45                 y1 = y0 - q * y1;
  46                 y0 = temp;
  47         */
  48     }
  49     x=x1;
  50 }
  51
  52 /* utiliza la ecuacion: a^2*x +a*b+b \equiv y
  53  * para despejar b, si no es posible, es porque el a no era correcto
  54  * b*(a+1) \equiv y -a^2
  55  */
  56 bool obtener_b(int a, int x, int y,int& b) {
  57     if ((a+1) % 73 == 0) {
  58         // para poder encontrar un b, la parte derecha tb tiene que ser congruente a 0 modulo 73
  59         if (y-resto(a*a,73)*x %73 != 0)return false;
  60         int amas1inv, aux;
  61         combinacion((a+1),137,amas1inv);
  62         amas1inv = resto(amas1inv,137);
  63
  64         int acuad = a*a %137;
  65         aux = resto((y - acuad*x),137);
  66         b = aux*amas1inv%137;
  67         return true;
  68     }
  69
  70     if ((a+1)%137 == 0) {
  71         // para poder encontrar un b, la parte derecha tb tiene que ser congruente a 0 modulo 137
  72         if (y-resto(a*a,137)*x %137 != 0)return false;
  73         int amas1inv, aux;
  74         combinacion((a+1),73,amas1inv);
  75         amas1inv = resto(amas1inv,73);
  76
  77         int acuad = a*a % 73;
  78         aux = resto((y - acuad*x),73);
  79         b = aux*amas1inv %73;
  80         return true;
  81     }
  82     int amas1inv137, aux;
  83
  84     combinacion((a+1),137,amas1inv137);
  85     amas1inv137 = resto(amas1inv137,137);
  86     int acuad137 = a*a % 137;
  87     int aux137 = resto((y - acuad137*x),137);
  88     int b137= aux137*amas1inv137 % 137;
  89     int amas1inv73;
  90     combinacion((a+1),73,amas1inv73);
  91     amas1inv73 = resto(amas1inv73,73);
  92     int acuad73 = a*a %73;
  93     int aux73 = resto((y - acuad73*x),73);
  94     int b73= aux73*amas1inv73 %73;
  95
  96     //usamos teorema chino del resto, para encontrar b
  97
  98     b = ((b73*coef_137)+(b137*coef_73)) % 10001;
  99
 100     return true;
 101
 102 }
 103
 104 static int numeros[101];
 105
 106 bool testear_candidato(int a, int b, int cant,list<int>& res) {
 107     forn(i,cant) {
 108         int f = (a*numeros[i]+b)% 10001;
 109         res.push_back(f);
 110         if (numeros[i+1] < cant && (a*f+b)% 10001 != numeros[i+1]) {
 111             break;
 112         }
 113     }
 114     return res.size() == cant;
 115 }
 116
 117 void llenar_res(int a,int a1,int x, int y,int cant,list<int>& res,int q) {
 118     int b;
 119     int candidatos[2] = {a,a1};
 120     int t = 0;
 121     while (true) {
 122         if (obtener_b(candidatos[t],x,y,b)) {
 123             if (testear_candidato(candidatos[t],b,cant,res))break;
 124         }
 125         res.clear();
 126         t++;
 127         if (t>1) {
 128             candidatos[0]=candidatos[0]+q;
 129             candidatos[1]=candidatos[1]+q;
 130             t=0;
 131         }
 132     }
 133 }
 134
 135 void resolver(const int cuadk[],int k,int x,int y,int qk, int wk,int cant) {
 136     int qkinv;
 137
 138     combinacion(qk,k,qkinv);
 139     qkinv = resto(qkinv,k);
 140     int acuad = (wk*qkinv)%k;
 141     int a,a1;
 142     a = cuadk[acuad];
 143     a1= k -cuadk[acuad];
 144     list<int> res;
 145     llenar_res(a,a1,x,y,cant,res,k);
 146     foreachin(it,res) {
 147         printf("%d\n",*it);
 148     }
 149 }
 150
 151
 152 int main(int argc, char** argv) {
 153     // cuad73[k] = a / a^2 % 73 == k
 154     // notar que alcanza mirar hasta 37 (73/2+1)
 155     // porque j^2 % 73 == (73 - j)^2
 156     // ademas no hay a1,a2 entre [0,73/2+1) tal que a1^2 % 73 == a2^2 % 73
 157     forn(each,37) {
 158         cuad73[(each*each)%73] = each;
 159
 160     }
 161     // simil a lo anterior
 162     forn(each,68) {
 163         cuad137[(each*each)%137]=each;
 164     }
 165     int cant;
 166     scanf("%d",&cant);
 167     while (cant > 0) {
 168
 169         forn(i,cant) {
 170             scanf("%d",&numeros[i]);
 171
 172         }
 173         if (cant < 3) {
 174             forn(i, cant) {
 175                 printf("%d\n",numeros[cant-1]);
 176             }
 177         }
 178         else {
 179             int x,y,z;
 180             x=numeros[0];
 181             y=numeros[1];
 182             z=numeros[2];
 183             int q,w;
 184             /* Idea:
 185              a*x + b \equiv 0_1
 186              a*O_1 + b \equiv y
 187              a*y + b \equiv O_2
 188              a*O_2 +b \equiv z
 189              -----------------
 190              a^2*x+ab+b \equiv y
 191              a^2*y+ab+b \equiv z
 192              --------------------
 193              a^2(x-y) \equiv (y-z)
 194
 195              Resolver esa ecuacion modulo 137 y 73 y obtener candidatos para a.
 196              obtener un b para alguno de los candidatos. usar esa pareja (a,b)
 197              */
 198             q = (x-y);
 199             w = (y-z);
 200
 201             int q137 = resto(q,137);
 202             int q73 = resto(q,73);
 203             int w137 = resto(w,137);
 204             int w73 = resto(w,73);
 205             if (q137 == 0) {
 206                 if (q73 == 0) {
 207                     forn(i,cant) {
 208                         printf("%d\n",numeros[cant-1]);
 209                     }
 210                 }
 211                 else {
 212                     resolver(cuad73,73,x,y,q73,w73,cant);
 213                 }
 214             }
 215             else {
 216                 if (q73 == 0) {
 217                     resolver(cuad137,137,x,y,q137,w137,cant);
 218                 }
 219                 else {
 220                     int q137inv,q73inv;
 221
 222                     combinacion(q137,137,q137inv);
 223                     q137inv = resto(q137inv,137);
 224                     int acuad137 = (w137*q137inv)%137;
 225                     combinacion(q73,73,q73inv);
 226                     q73inv = resto(q73inv,73);
 227                     int acuad73 = (w73*q73inv)%73;
 228                     int a,b;
 229                     int j = cuad73[acuad73];
 230                     int k = cuad137[acuad137];
 231                     list<int> res;
 232                     int candidatos[4] = { resto(j*coef_137 + k* coef_73,10001), resto((73-j)*coef_137 + k* coef_73,10001),
 233                                           resto((73-j)*coef_137 + (137-k)* coef_73,10001), resto(j*coef_137 + (137-k)* coef_73,10001)
 234                                         };
 235                     forn(i, 4) {
 236                         a =candidatos[i] ;
 237                         if (obtener_b(a,x,y,b)) {
 238                             if (testear_candidato(a,b,cant,res)) {
 239                                 break;
 240                             }
 241                         }
 242                         res.clear();
 243                     }
 244                     foreachin(it,res) {
 245                         printf("%d\n",*it);
 246                     }
 247
 248                 }
 249             }
 250
 251         }
 252         if (scanf("%d\n",&cant)!=1)break;
 253     }
 254     return (EXIT_SUCCESS);
 255 }
 256